class Solution {
    //单词替换字典树做法
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] split = sentence.split(" ");
        // 前缀加入字典树
        for (String ss : dictionary) {
            insert(ss);
        }
        StringBuilder ret = new StringBuilder();
        for (String s : split) {
            //找到最短前缀str
            String str = shortestPrex(s);
            if (str.equals("")) {
                ret.append(s);
            } else {
                ret.append(str);
            }
            ret.append(" ");
        }
        ret.deleteCharAt(ret.length() - 1);
        return ret.toString();
    }

    class TrieNode {
        boolean val;
        TrieNode[] child = new TrieNode[26];
    }

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode p = root;
        for(char c:word.toCharArray()) {
            int i = c - 'a';

            if(p.child[i] == null) p.child[i] = new TrieNode();

            p = p.child[i];
        }
        p.val = true;
    }

    //找最短前缀和数组
    public String shortestPrex(String word) {
        TrieNode p = root;
        StringBuilder sb = new StringBuilder();
        for(char c:word.toCharArray()) {
            if(p.val) return sb.toString();
            int i = c - 'a';
            sb.append(c);
            if(p.child[i] == null) return "";
            p = p.child[i];
        }
        return "";
    }
}